/* eslint-disable no-param-reassign */
/* eslint-disable operator-assignment */
/**
 * 计数排序
 * @param A 需要被排序的数组
 * @param B 排序结果
 * @param k A的元素在0..k之间的整数。
 */
export function countingSort(A: number[], B: number[], k: number): number[] {
	// 临时存储区[0..k]
	const C = Array<number>(k + 1).fill(0)
	// 在临时存储区中，记录A的元素出现的次数
	for (let j = 0; j < A.length; j += 1) {
		C[A[j]] += 1
	}

	// 在临时存储区中，对于[0..k]每个值，A中小于等于这个值的元素个数。
	// C[5]表示A中小于等于5的元素个数，假设是3，说明5是第3小元素，应该放到B[2]里。
	for (let j = 1; j <= k; j += 1) {
		C[j] += C[j - 1]
	}

	for (let j = A.length - 1; j >= 0; j -= 1) {
		// C[5]表示A中小于等于5的元素个数，假设是3，说明5是第3小元素，应该放到B[2]里。
		B[C[A[j]] - 1] = A[j]
		// 用于处理A中重复出现的值。
		C[A[j]] -= 1
	}

	return B
}

console.log(countingSort([7, 5, 5, 1], [], 7))
